#include <iostream>
#include <vector>
using namespace std;

typedef struct _tree_node {
	int value;
	struct _tree_node* left;
	struct _tree_node* right;

	_tree_node(int val) {
		value = val;
		left = NULL;
		right = NULL;
	}
}tree_node;

bool get_path(tree_node* root, tree_node* end, vector<tree_node*>& path) {
	if (root==NULL)
		return false;

	if (root == end) {
		path.push_back(root);
		return true;
	}

	path.push_back(root);
	bool found = get_path(root->left, end, path);
	if (!found) 
		found = get_path(root->right, end, path);

	if (!found) {
		path.pop_back();
		return false;
	}
	else
		return true;
}

tree_node* low_common(tree_node* root, tree_node* end1, tree_node* end2) {
	vector<tree_node*> path1;
	vector<tree_node*> path2;

	get_path(root, end1, path1);
	get_path(root, end2, path2);
	
	vector<tree_node*>::iterator iter1 = path1.begin();
	vector<tree_node*>::iterator iter2 = path2.begin();

	tree_node* common = NULL;
	while (iter1!=path1.end() && iter2!=path2.end()){
		if ((*iter1)->value == (*iter2)->value) {
			common = *iter1;
		}

		iter1++;
		iter2++;
	}

	return common;
}

int main() {
	tree_node* r0 = new tree_node(0);
	tree_node* r1 = new tree_node(1);
	tree_node* r2 = new tree_node(2);
	tree_node* r3 = new tree_node(3);
	tree_node* r4 = new tree_node(4);
	tree_node* r5 = new tree_node(5);
	tree_node* r6 = new tree_node(6);
	tree_node* r7 = new tree_node(7);
	tree_node* r8 = new tree_node(8);
	tree_node* r9 = new tree_node(9);

	r0->left  = r1;
	r0->right = r2;
	r1->left  = r3;
	r1->right = r4;
	r2->left  = r5;
	r3->left  = r6;
	r4->left  = r7;
	r7->right = r9;
	r5->right = r8;	
	tree_node* root = r0;
	
	tree_node* ance = low_common(root, r8, r9);
	return 0;
}